package lc.q51_100;


import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
 */
public class Q95 {

    public List<TreeNode> generateTrees(int n) {
        // 根节点位1的方案。。。。n的方案
        // 变成(1..k-1)的树的方案和(k+1..n)的树的方案
        // 使用数组代替，最后遍历数组，免得麻烦
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        if (start > end) {
            // 返回一个null节点
            nodes.add(null);
            return nodes;
        }
        // 当前节点
        for (int i = start; i <= end; i++) {
            // 生成左节点
            List<TreeNode> left = generateTrees(start, i-1);
            List<TreeNode> right = generateTrees(i + 1, end);
            for (TreeNode treeNode : left) {
                for (TreeNode node : right) {
                    TreeNode currentNode = new TreeNode(i);
                    currentNode.left = treeNode;
                    currentNode.right = node;
                    nodes.add(currentNode);
                }
            }
        }
        return nodes;
    }

}
